import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/*
三数之和
采用定一移二，从最小的开始。
剩下两个数采用两数之和的思路解决
 */
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n=nums.length;

        List<List<Integer>> list=new ArrayList<>();

        Arrays.sort(nums);

        for(int i=0;i<n;){
            if(nums[i]>0){
                break;
            }
            int j=i+1,k=n-1;
            while(j<k){
                if(nums[i]+nums[j]+nums[k]>0){
                    k--;
                }else if(nums[i]+nums[j]+nums[k]<0){
                    j++;
                }else{
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[k])));
                    k--;
                    j++;
                    while(nums[j]==nums[j-1] && j<k){
                        j++;
                    }
                    while(nums[k]==nums[k+1] && j<k){
                        k--;
                    }
                }
            }

            i++;
            while(i<n && nums[i]==nums[i-1]){
                i++;
            }
        }
        return list;
    }
}